package com.cb2.algorithm.leetcode;

/**
 * <a href="https://leetcode.cn/problems/reverse-nodes-in-k-group/">K 个一组翻转链表(Reverse Nodes in k-Group)</a>
 * <p>给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
 * k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
 * 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：head = [1,2,3,4,5], k = 2
 *      输出：[2,1,4,3,5]
 *
 * 示例 2：
 *      输入：head = [1,2,3,4,5], k = 3
 *      输出：[3,2,1,4,5]
 * </pre>
 * </p>
 * <p>
 * <b>提示：</b>
 * <ul>
 * <li>链表中的节点数目为 n</li>
 * <li>1 <= k <= n <= 5000</li>
 * <li>0 <= Node.val <= 1000</li>
 * </ul>
 * </p>
 * <br><b>进阶：你可以设计一个只用 O(1) 额外内存空间的算法解决此问题吗？</b>
 *
 * @author c2b
 * @since 2023/5/5 9:20
 */
public class LC0025ReverseNodesInKGroup_H {

    static class Solution {

        public ListNode reverseKGroup(ListNode head, int k) {
            // 特殊情况：1个节点反转等于没反转
            if (k == 1) {
                return head;
            }
            // 统计总共有多少节点，可以分成多少组
            int totalNodeCount = 0;
            ListNode currNode = head;
            while (currNode != null) {
                ++totalNodeCount;
                currNode = currNode.next;
            }
            ListNode resultDummyNode = new ListNode(-1);
            ListNode resultCurrNode = resultDummyNode;
            // 组数 group = nodeCount/k，因为不满一组不需要反转
            for (int i = 0; i < totalNodeCount / k; ++i) {
                currNode = head;
                for (int j = 0; j < k - 1; ++j) {
                    currNode = currNode.next;
                }
                // 下一组的头节点
                ListNode nextGroupHeadNode = currNode.next;
                // 断开并反转
                currNode.next = null;
                resultCurrNode.next = reverse(head);
                while (resultCurrNode.next != null) {
                    resultCurrNode = resultCurrNode.next;
                }
                // 更新为head下一组的头节点：准备下一组的反转
                head = nextGroupHeadNode;
            }
            // 特殊处理可能存在的不满一组的节点
            resultCurrNode.next = head;
            return resultDummyNode.next;
        }

        public ListNode reverseKGroup2(ListNode head, int k) {
            // 特殊情况：1个节点反转等于没反转
            if (k == 1) {
                return head;
            }
            ListNode dummyHead = new ListNode(-1, head);
            // currGroupPrevNode：用于记录当前组的头节点的前一个节点
            // currGroupTailNode：用于记录当前组的尾节点
            ListNode currGroupPrevNode = dummyHead;
            ListNode currGroupTailNode;
            while (currGroupPrevNode.next != null) {
                currGroupTailNode = currGroupPrevNode;
                // 从当前节点开始，向后找到 K 个节点，记为一组。如果当前组节点数不足 K 个，不需要反转
                for (int i = 0; i < k && currGroupTailNode != null; i++) {
                    currGroupTailNode = currGroupTailNode.next;
                }
                // ==> 特殊情况：当前组节点数量不足K个。结束循环
                if (currGroupTailNode == null) {
                    break;
                }

                // 记录当前组的头节点。反转后会变成尾节点(即下一组头节点的上一个节点)，用于与下一组的头节点拼接
                ListNode currGroupHeadNodeBeforeReserve = currGroupPrevNode.next;
                // 1.断开链表。记录下一组的头节点，让当前组的尾节点指向null
                ListNode nextGroupHeadNode = currGroupTailNode.next;
                currGroupTailNode.next = null;
                // 2.反转链表 并 进行连接
                currGroupPrevNode.next = reverse(currGroupPrevNode.next);
                currGroupHeadNodeBeforeReserve.next = nextGroupHeadNode;
                // 来到下一组
                currGroupPrevNode = currGroupHeadNodeBeforeReserve;
            }
            return dummyHead.next;
        }

        private ListNode reverse(ListNode listNode) {
            ListNode prevNode = null;
            ListNode currNode = listNode;
            ListNode nextNode;
            while (currNode != null) {
                nextNode = currNode.next;
                currNode.next = prevNode;
                prevNode = currNode;
                currNode = nextNode;
            }
            return prevNode;
        }
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);

        ListNode head2 = new ListNode(1);
        head2.next = new ListNode(2);
        head2.next.next = new ListNode(3);
        head2.next.next.next = new ListNode(4);
        head2.next.next.next.next = new ListNode(5);

        Solution solution = new Solution();
        // 2 -> 1 -> 4 -> 3 -> 5 -> null
        Printer.printListNode(solution.reverseKGroup(head, 2));
        // 3 -> 2 -> 1 -> 4 -> 5 -> null
        Printer.printListNode(solution.reverseKGroup(head2, 3));
    }
}